import java.util.HashMap;
import java.util.Map;

/**
 * 138. 复制带随机指针的链表
 * https://leetcode-cn.com/problems/copy-list-with-random-pointer/
 */
public class Solutions_138 {
    public static void main(String[] args) {
        Node_138 node0 = new Node_138(7);
        Node_138 node1 = new Node_138(13);
        Node_138 node2 = new Node_138(11);
        Node_138 node3 = new Node_138(10);
        Node_138 node4 = new Node_138(1);

        node0.next = node1;
        node1.random = node0;
        node1.next = node2;
        node2.next = node3;
        node2.random = node4;
        node3.next = node4;
        node3.random = node2;
        node4.random = node0;  // input:{{7, null}, {13, 0}, {11, 4}, {10, 2}, {1, 0}}
                                // ouput:{{7, null}, {13, 0}, {11, 4}, {10, 2}, {1, 0}}

        Node_138 result = copyRandomList(node0);
        System.out.println(result);
    }

    public static Node_138 copyRandomList(Node_138 head) {
        Node_138 cur = head;
        Map<Node_138, Node_138> map = new HashMap<>();
        while (cur != null) {
            // 将原结点与复制结点映射到 map 中
            Node_138 clone = new Node_138(cur.val);
            map.put(cur, clone);
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            // 将复制结点的 next 和 random 关系，与原结点保持一致，但是关系仍然是复制结点与复制结点之间的关系，即
            // map.get(cur) 获取的结点
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}

class Node_138 {
    int val;
    Node_138 next;
    Node_138 random;

    public Node_138(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
